\section{Related Work}
Although the problem
\[
Pm~\vert~\vert \sum w_jU_j
\]
is $\mathcal{NP}$--hard, it is solvable in pseudo-polynomial time by applying the dynamic programming techniques of Rothkopf \cite{rothkopf1966sit} and Lawler and Moore \cite{lawler1969fea}. That algorithm require $O(n(\sum p_j)^m)$ running time and space, so as the problem size grows, this algortihm becomes impractical, especially the running space will become a problem.

Then Van den Akker \cite{vandenakker1999pms} and Chen \cite{chen1999spm} solved that problem using the method of \emph{column generation}. The major contribution of their work is to view the problem as a \emph{partitioning} problem. It takes the first step to partition jobs into $m$ subsets, each subset of jobs can be assigned to any single machine. However, it is hard to apply this method to our problem because one feasible subset of on time jobs on one machine may not be feasible on another machine since time windows differ.
